package 单调栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class LeetCode503_下一个更大元素2 {
    // 没说没有重复元素
    public static int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];
        for (int i = 0; i < result.length; i++) {
            result[i] = -1;
        }
        Stack<Integer> st = new Stack<>();

        for(int i = 0; i < length * 2-1; i++) {
            while(!st.isEmpty() && nums[st.peek()] < nums[i%length]) {
                result[st.pop()] = nums[i%length];
            }
            if(i < nums.length) {
                st.push(i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {100,1,11,1,120,111,123,1,-1,-100};
        int[] resule = nextGreaterElements(nums);

        System.out.println(resule);
    }
}
